package yao.xerophyte.java.algorithm.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 冒泡排序
 *
 * @author yaojx
 */
public class Bubble {
    public static void main(String[] args) {
        int length = 10000;
        int[] sortArray1 = generateRandomArr(length);
        int[] sortArray1Check = new int[sortArray1.length];
        System.arraycopy(sortArray1, 0, sortArray1Check, 0, sortArray1.length);
        Arrays.sort(sortArray1Check);
        bubbleSortBase(sortArray1);
        System.out.println("排序结果是否正确：" + check(sortArray1, sortArray1Check));
        
        int[] sortArray2 = generateRandomArr(length);
        int[] sortArray2Check = new int[sortArray2.length];
        System.arraycopy(sortArray2, 0, sortArray2Check, 0, sortArray2.length);
        Arrays.sort(sortArray2Check);
        bubbleSortOptimization(sortArray2);
        System.out.println("验证最优情况下的时间复杂度");
        bubbleSortOptimization(sortArray2);
        System.out.println("排序结果是否正确：" + check(sortArray2, sortArray2Check));
        
    }
    
    /**
     * 冒泡排序基础实现
     *
     * @param sortArray
     */
    private static void bubbleSortBase(int[] sortArray) {
        System.out.println("==============基础实现冒泡排序：");
        int count = 0;
        for (int i = 1; i < sortArray.length; i++) {
            for (int sortIndex = 0; sortIndex < sortArray.length - i; sortIndex++) {
                if (sortArray[sortIndex] > sortArray[sortIndex + 1]) {
                    changePosition(sortArray, sortIndex, sortIndex + 1);
                }
                count++;
            }
        }
        System.out.println("循环了：" + count);
//        printArray(sortArray);
    }
    
    /**
     * 使冒泡排序在最优情况下时间复杂度为O(n)
     *
     * @param sortArray
     */
    private static void bubbleSortOptimization(int[] sortArray) {
        System.out.println("==============优化后的冒泡排序：");
        int count = 0;
        boolean isPerfect = true;
        for (int i = 1; i < sortArray.length; i++) {
            if (i == 1 || !isPerfect) {
                for (int sortIndex = 0; sortIndex < sortArray.length - i; sortIndex++) {
                    if (sortArray[sortIndex] > sortArray[sortIndex + 1]) {
                        isPerfect = false;
                        changePosition(sortArray, sortIndex, sortIndex + 1);
                    }
                    count++;
                }
            }
        }
        System.out.println("循环了：" + count);
//        printArray(sortArray);
    }
    
    /**
     * 生产随机样本
     *
     * @param length 指定数组长度
     * @return 指定长度的数组样本
     */
    private static int[] generateRandomArr(int length) {
        Random random = new Random();
        int[] sortArray = new int[length];
        for (int i = 0; i < sortArray.length; i++) {
            sortArray[i] = random.nextInt(length);
        }
        return sortArray;
    }
    
    /**
     * 校验两个数组是否相等
     *
     * @param sortArray1 数组1
     * @param sortArray2 数组2
     * @return 是否相等
     */
    private static boolean check(int[] sortArray1, int[] sortArray2) {
        if (sortArray1 == null || sortArray2 == null || sortArray1.length != sortArray2.length) {
            return false;
        }
        for (int i = 0; i < sortArray1.length; i++) {
            if (sortArray1[i] != sortArray2[i]) {
                System.out.println("对数错误，index=" + i);
                return false;
            }
        }
        return true;
    }
    
    /**
     * 交换数组中两个元素的位置
     *
     * @param arraySrc    需要交换的数组
     * @param firstIndex  位置1
     * @param secondIndex 位置2
     */
    private static void changePosition(int[] arraySrc, int firstIndex, int secondIndex) {
        int tempValue = arraySrc[firstIndex];
        arraySrc[firstIndex] = arraySrc[secondIndex];
        arraySrc[secondIndex] = tempValue;
    }
    
    /**
     * 打印数组
     *
     * @param arraySrc 需要打印的数组
     */
    private static void printArray(int[] arraySrc) {
        StringBuilder stringBuilder = new StringBuilder("[");
        if (arraySrc != null && arraySrc.length > 0) {
            for (int i = 0; i < arraySrc.length; i++) {
                stringBuilder.append(arraySrc[i]);
                if (i != arraySrc.length - 1) {
                    stringBuilder.append(",");
                } else {
                    stringBuilder.append("]");
                }
            }
        } else {
            stringBuilder.append("]");
        }
        System.out.println(stringBuilder.toString());
    }
}
